from functools import cache


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n = len(s)
        m = len(p)

        # 当前操作作为最终状态，考虑怎么递归到前一个状态
        @cache
        def dfs(i, j):

            if i < 0:
                # 正常情况匹配完全
                if j < 0:
                    return True
                # 有 * 的情况
                if p[j] != "*":
                    return False
                # 有 * , 匹配多个的情况,把j递归到 j<0,如果中途有一个 不等于 * 返回False
                return dfs(i, j - 1)
            if j < 0 and i >= 0:
                return False

            # 先匹配简单的
            # 匹配单个字符
            if s[i] == p[j] or p[j] == "?":
                return dfs(i - 1, j - 1)
            # 复杂的匹配
            elif p[j] == "*":
                # 可以匹配 空 单个 多个(三个，四个。。。)
                return dfs(i, j - 1) or dfs(i - 1, j - 1) or dfs(i - 1, j)
            # 不匹配
            else:
                return False

        # 最终状态
        return dfs(n - 1, m - 1)


# 方法二：
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n = len(s)
        m = len(p)

        dp = [[False] * (m + 1) for _ in range(n + 1)]

        # 初始条件：翻译自递归边界
        # 对应边界 i<0 and j<0 return True
        dp[0][0] = True
        # 对应边界 i<0 j>=0 的处理
        # 有 * 的情况
        #         if p[j] !="*":
        #             return False
        #         # 有 * , 匹配多个的情况,把j递归到 j<0,如果中途有一个 不等于 * 返回False
        #         return dfs(i,j-1)
        for j in range(m):
            dp[0][j + 1] = p[j] == "*" and dp[0][j]

        # 对应边界 j<0 (f初始化已经赋值了False, 不用写)
        # for i in range(m):
        #     f[i + 1][0] = False

        # dp翻译自状态转移
        for i in range(n):
            for j in range(m):
                if s[i] == p[j] or p[j] == "?":
                    dp[i + 1][j + 1] = dp[i][j]
                elif p[j] == '*':
                    dp[i + 1][j + 1] = dp[i][j + 1] or dp[i + 1][j]

        return dp[n][m]



